﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Middle_15_ThreeSum
{
    class MainProjecet
    {
        static void Main(string[] args)
        {
            foreach (var item in ThreeSum(new int[] {-2,-3,0,0,-2 }))//-4 -1 -1 0 1 2
            {
                Console.WriteLine("{0}:{1}:{2}", item[0], item[1], item[2]);
                Console.WriteLine("----分隔符----");
            }

            Console.ReadKey();
        }
        public static IList<IList<int>> ThreeSum(int[] nums)
        {

            #region 暴力超时
            //暴力法(超时)--优化
            //优化方向--减少循环次数（用空间换时间）
            //IList<IList<int>> lists = new List<IList<int>>();
            //if (nums.Length <= 2) return lists;

            //Array.Sort(nums);

            //HashSet<int> hashx = new HashSet<int>();
            //HashSet<int> hashy = new HashSet<int>();
            //HashSet<int> hashz = new HashSet<int>();

            //for (int i = 0; i < nums.Length; i++)
            //{
            //    if (!hashx.Add(nums[i]))
            //    {
            //        continue;
            //    }
            //    hashy.Clear();
            //    for (int j = i + 1; j < nums.Length; j++)
            //    {
            //        if (!hashy.Add(nums[j]))
            //        {
            //            continue;
            //        }
            //        hashz.Clear();
            //        for (int k = j + 1; k < nums.Length; k++)
            //        {
            //            if (!hashz.Add(nums[k]))
            //            {
            //                continue;
            //            }
            //            if (nums[i] + nums[j] + nums[k] == 0)
            //            {
            //                lists.Add(new List<int>() { nums[i], nums[j], nums[k] });
            //            }
            //        }
            //    }
            //}
            ////lists.GroupBy(i=>i.)
            //return lists;
            #endregion

            #region 排序+双指针
            IList<IList<int>> lists = new List<IList<int>>();
            Array.Sort(nums);

            int firstIndex = 1;
          
            int secondIndex = nums.Length - 1;
            int sum = 0;
            for (int i = 0; i < nums.Length; i++)
            {
                while (firstIndex< secondIndex)
                {
                    sum = nums[i] + nums[firstIndex] + nums[secondIndex];
                    if (sum == 0)
                    {
                        lists.Add(new List<int>() { nums[i], nums[firstIndex], nums[secondIndex] });
                        if (firstIndex + 1 < nums.Length)
                        {
                            firstIndex++;
                            while (nums[firstIndex - 1] == nums[firstIndex])
                            {
                                firstIndex++;
                                if (firstIndex >= nums.Length)
                                {
                                    break;
                                }
                            }
                        }

                        secondIndex--;
                        while (nums[secondIndex] == nums[secondIndex + 1])
                        {
                            secondIndex--;
                            if (secondIndex < 0)
                            {
                                break;
                            }
                        }
                    }
                    else if (sum > 0)
                    {
                        secondIndex--;
                        while (nums[secondIndex] == nums[secondIndex + 1])
                        {
                            secondIndex--;
                            if (secondIndex<0)
                            {
                                break;
                            }
                        }
                    }
                    else
                    {
                        if (firstIndex + 1< nums.Length)
                        {
                            firstIndex++;
                            while (nums[firstIndex - 1] == nums[firstIndex])
                            {
                                firstIndex++;
                                if (firstIndex >= nums.Length)
                                {
                                    break;
                                }
                            }
                        }
                      
                    }
                }
                if (i+1< nums.Length)
                {
                    while (nums[i] == nums[i + 1])
                    {
                        i++;
                        if (i+1>= nums.Length)
                        {
                            break;
                        }
                    }
                    firstIndex = i + 2;
                    secondIndex = nums.Length - 1;
                }
            }
            return lists;
            #endregion
        }
    }
}
